//
//  BBBlobDetector.m
//  BBVImageTest
//
//  Created by ben smith on 5/27/08.
//  This file is part of BBTouch.
//
//  BBTouch is free software: you can redistribute it and/or modify
//  it under the terms of the GNU Lesser General Public License as published by
//  the Free Software Foundation, either version 3 of the License, or
//  (at your option) any later version.

//  BBTouch is distributed in the hope that it will be useful,
//  but WITHOUT ANY WARRANTY; without even the implied warranty of
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//  GNU Lesser General Public License for more details.

//  You should have received a copy of the GNU Lesser General Public License
//  along with BBTouch.  If not, see <http://www.gnu.org/licenses/>.
// 
//  Copyright 2008 Ben Britten Smith ben@benbritten.com .
//

#import "BBBlobDetector.h"
#import "BBImagePreProcessor.h"
#import "BBPixelBlob.h"
#import "BBConfigurationController.h"

// this is based on the algo described by:
//A Linear-Time Component-Labeling Algorithm 
//Using Contour Tracing Technique 
//Fu Chang, Chun-Jen Chen, and Chi-Jen Lu 
//Institute of Information Science, Academia Sinica 
//128 Academia Road, Section 2, Nankang, Taipei 115 Taiwan 
//E-mail: fchang@iis.sinica.edu.tw, dean@iis.sinica.edu.tw, cjlu@iis.sinica.edu.tw 
// originally found here:
// http://www.iis.sinica.edu.tw/~fchang/paper/component_labeling_cviu.pdf  

// it is not a simple algorithm by any means, and you should read the paper if
// the code and comments here are going to make sense whatsoever


@implementation BBBlobDetector

@synthesize invert;

- (id) init
{
	self = [super init];
	if (self != nil) {
		// fill the blob array with 2000 premade blobs
		// TODO: add a check in the code somewhere to make sure we never overrun this amount
		// and if we do to either fail gracefully (usually if you get into the 2000 blob range, then something has gone wrong with the video) 
		// or add more blobs as appropriate
		blobs = [[NSMutableArray alloc] init];
		filteredBlobs = [[NSMutableArray alloc] init];
		int i;
		for (i = 0; i < 4000; i ++) {
			[blobs addObject:[BBPixelBlob pixelBlob]];
		}
		labelIndex = 0;
	}
	return self;
}



-(void)setThreshold:(int)aThresh
{
	threshold = aThresh;
}

-(int)threshold
{
	return threshold;
}

-(void)setupNeighborGrid
{
	// sets the 'neighbor' values
	// the center pos => positionInByteArray = (yIndex * bytesPerRow) + xIndex;
	// we want the grid to give us byte offsets to get to the neighbor pixels
	// the grid is indexes like so:
	// 5 6 7
	// 4 P 0
	// 3 2 1
	// where P is our point
	// this way I can get the point directly above my current point with : positionInByteArray + neighborGrid[6];
	// simple and fast
	neighborGrid[0] = samplesPerPixel;
	neighborGrid[1] = bytesPerRow + samplesPerPixel;
	neighborGrid[2] = bytesPerRow;
	neighborGrid[3] = bytesPerRow - samplesPerPixel;
	neighborGrid[4] = 0 - samplesPerPixel;
	neighborGrid[5] = 0 - bytesPerRow - samplesPerPixel;
	neighborGrid[6] = 0 - bytesPerRow;
	neighborGrid[7] = 0 - bytesPerRow + samplesPerPixel;
	
	// xGrid gives me the offset for the x values for any given neighbor index
	xGrid[0] = 1;
	xGrid[1] = 1;
	xGrid[2] = 0;
	xGrid[3] = -1;
	xGrid[4] = -1;
	xGrid[5] = -1;
	xGrid[6] = 0;
	xGrid[7] = 1;

	// yGrid gives me the offset for the y values for any given neighbor index
	// note: y is flipped
	yGrid[0] = 0;
	yGrid[1] = 1;
	yGrid[2] = 1;
	yGrid[3] = 1;
	yGrid[4] = 0;
	yGrid[5] = -1;
	yGrid[6] = -1;
	yGrid[7] = -1;
}


-(void)setupStateArrays
{
	// a 0 will be an unvisited pixel (they all start that way)
	// a -1 will be a non-blob pixel
	// > 0 will be a blob pixel (will start at 255 and go down from there, that way we can use the resulting
	// bitmap to actually see the blobs we have detected)
	free(labels); 
	labels = malloc((pixelsWide * pixelsHigh) * sizeof(int));
	if (labels == NULL) { //die
		NSLog(@"cannot allocate memory");
		return;
	}
	[self clearStateArray];
}

-(void)clearStateArray
{
	memset(labels, 0, pixelsWide * pixelsHigh * sizeof(int));		
	[blobs makeObjectsPerformSelector:@selector(reset)];
	[blobs makeObjectsPerformSelector:@selector(setInvert:) withObject:[NSNumber numberWithBool:invert]];
}

// the main method, loads all the right structures and starts the scan
// i will try and keep this as simple as possible, and then, if it works, I will make optimizations from there
// first off, we need to be able to scan through each and every pixel in the image
-(void)analyze:(NSImage*)anImage
{
	if (bgImage == nil) return; // cant do anything without a background image
	
	NSBitmapImageRep * bitRep = [[anImage representations] objectAtIndex:0];
	
	NSBitmapImageRep * bgBitRep = [[bgImage representations] objectAtIndex:0];

	if (self.invert) {
		[BBImagePreProcessor borderROI:bitRep roi:roi colorValue:255];
		bgBytes = [bitRep bitmapData];
		srcBytes = [bgBitRep bitmapData];
	} else {
		[BBImagePreProcessor borderROI:bitRep roi:roi colorValue:0];
		srcBytes = [bitRep bitmapData];
		bgBytes = [bgBitRep bitmapData];		
	}
	
	[self analyzeRawData];
}


// this is the generic alayze method.  you call this once you have data 'loaded' into srcBytes and bgBytes
-(void)analyzeRawData 
{
	// i am presuming for now that the data is planar 8 monochrome 

	//set up the label array
	[self clearStateArray];
	// scan the data
  //	[self scanSrcData]; // this is the old method
	[self	scanSrcDataWithROI];
	
	[self filter];
	// debug
//	[self printBlobs];	
}

-(void)filter
{
	// TODO: cache this, dont need to get it each time
	float minRadius = [[BBConfigurationController objectForSettingKey:@"BBBlobMinimunRadius"] floatValue];

	[filteredBlobs removeAllObjects];
	// first blob is a wash since the index = label = 0 = an unmarked pixel, so we just ignore it
	int i;
	for (i = 1; i < labelIndex; i++) {
		if ([[blobs objectAtIndex:i] radius] > minRadius) {
			[filteredBlobs addObject:[blobs objectAtIndex:i]];
		}
	}
}


-(void)printBlobs
{
	// first blob is a wash since the index = label = 0 = an unmarked pixel, so we just ignore it
	int i;
	for (i = 1; i < labelIndex; i++) {
		NSLog(@"%@",[blobs objectAtIndex:i]);
	}
}

-(NSArray*)blobs
{
	return filteredBlobs;
}

-(void)setROI:(NSRect)aRect
{
	// cache some useful infor about the ROI so i dont need to do it every time
	// saves a very small amount of cycles, possibly not worth it
	roi = aRect;
	yMin = NSMinY(roi);
	yMax = NSMaxY(roi);
	xMax = NSMaxX(roi);
	xMin = NSMinX(roi);
}

-(void)scanSrcDataWithROI
{
	// run it like a state machine, set the state variables, then call the right functions
	// nested for loops; to scan through the entire image
	labelIndex = 1; // the labeling number for our blobs
	for (loopY = yMin; loopY < yMax; loopY++) {
		for (loopX = xMin; loopX < xMax; loopX++) {
			loopXYDataPosition = (loopY * bytesPerRow) + (loopX * samplesPerPixel);
			// the vast majority of pixels will be 'bad' ones and those just need to be marked
			// and move on
			// note, if you change this then you should also change validBlobPixel:
			if ((srcBytes[loopXYDataPosition] - bgBytes[loopXYDataPosition]) <= threshold) {
				// bad move on
				labels[(loopY * pixelsWide) + loopX] = -1;
				continue;
			}
			// some are 'good' pixels
			[self handleGoodPixel];
		}
	}	
}

-(void)handleGoodPixel
{	
	// this will be handy
	int statePosition = ((loopY * pixelsWide) + loopX);
	// ok, step 1: if our current pixel is UNMARKED and the pixel above it is a non-blob.. '6' is right above
	if ((labels[statePosition] == 0) && (![self validLoopPixelAbove])) {
		// then we start a new external contour
		// this is a new blob, so make a new label
		contourLabel = labelIndex;
		if ([self externalContour]) labelIndex++;
		// dont return here, it may be that step 2 is also valid
	}

	// step 2: if the pixel below this one is an UNMARKED non-blob
	
	int statePositionBelow = ((loopY + 1) * pixelsWide) + loopX;
	if ((labels[statePositionBelow] == 0) && ![self validLoopPixelBelow]) {
	
		// first figure out the label for our current pixel
		if (labels[statePosition] == 0) { // if it is unmarked, then it must be the same as the pixel to the left
			labels[statePosition] = labels[statePosition - 1]; 
			// whenever we label something a blob pixel, we should add it to the appropriate blob
			[[blobs objectAtIndex:labels[statePosition - 1]] addPixel:NSMakePoint(loopX, loopY)  withValue:srcBytes[loopXYDataPosition]];		
		}
		// now we start a new internal contour
		contourLabel = labels[statePosition]; // same as current label 
		[self internalContour];
		return; // shunt
	} 

	// step 3, if it isnt one of the above, and it is NOT already marked then it is a 
	// blob pixel and the label should match the one to the left

	if (labels[statePosition] == 0) {
		// whenever we label something a blob pixel, we should add it to the appropriate blob
		labels[statePosition] = labels[statePosition - 1];
		[[blobs objectAtIndex:labels[statePosition - 1]] addPixel:NSMakePoint(loopX, loopY) withValue:srcBytes[loopXYDataPosition]];					
	}

}


// some convenience functions
// if you wanted a small performance increase, move this code into the body of the algorythm
-(BOOL)validLoopPixel
{
	return [self validBlobPixel:loopXYDataPosition];
}

-(BOOL)validLoopPixelAbove
{
	return [self validBlobPixel:loopXYDataPosition + neighborGrid[6]];
}

-(BOOL)validLoopPixelBelow
{
	return [self validBlobPixel:loopXYDataPosition + neighborGrid[2]];
}

-(BOOL)validContourPixel
{
	return [self validBlobPixel:contourXYDataPosition];
}

-(BOOL)validNeighborPixel
{
	return [self validBlobPixel:contourXYDataPosition + neighborGrid[contourNeighborCheckIndex]];
}

-(BOOL)validBlobPixel:(int)position
{
	// note, if you change this then you should also change scanSrc
	// they both have the check for 'goodness'
	// this double-code is for performance

	if (( position < 0 ) || (position >= maxDataPosition)) {
		NSLog(@"position Out of bounds %d",position);
		return NO;
	}
	if ((srcBytes[position] - bgBytes[position]) > threshold) {
		return YES;
	}
	return NO;
}




// this changes the state of the contour machine, moving it to the specified neighbor index
-(void)moveContourStateToNeighbor:(int)neighborIndex
{
	contourXYDataPosition += neighborGrid[neighborIndex];
	contourX += xGrid[neighborIndex];
	contourY += yGrid[neighborIndex];
}

// finds the contour of the blob
-(BOOL)contour
{
	// set initial conditions
	contourX = loopX;
	contourY = loopY;
	contourXYDataPosition = loopXYDataPosition;
		
	// find our first neighbor, we need this later to tell if we are done
	int contourFirstNeighbor = [self findNextNeighbor];	
	if (contourFirstNeighbor == -1) {
		// this 'blob' is just an isolated pixel
		// throw it out
		labels[(contourY * pixelsWide) + contourX] = -1;
		return NO; //shunt
	}

	// this is a blob then so label our start pixel, if it isnt already
	// (internal contours usually start with pixel that are already labeled
	if (labels[(contourY * pixelsWide) + contourX] == 0) {
		labels[(contourY * pixelsWide) + contourX] = contourLabel;
		[[blobs objectAtIndex:contourLabel] addPixel:NSMakePoint(contourX, contourY)  withValue:srcBytes[contourXYDataPosition]];		
	}

	// now we have our initial points, start the iterations
	// the odd thing about this loop is the assignment of contourNeighborCheckIndex
	// it is meant to be 2 positions clockwise from the direction of the last
	// neighbor pixel.  When we come into the loop, contourNeighborCheckIndex is 'pointing'
	// toward the pixel we just moved to form the last pixel, so really we want to go
	// 2 step anti-clockwise from this position. (or 6 positions clockwise, modded)
	
	int nextNeighbor;
	BOOL done = NO;
	do {
		// move the contour to the found neighbor pixel
		[self moveContourStateToNeighbor:contourNeighborCheckIndex];
		// update the checkIndex
		contourNeighborCheckIndex = (contourNeighborCheckIndex + 6) % 8;
		// look for the next neighbor
		nextNeighbor = [self findNextNeighbor];	// this will alter contourNeighborCheckIndex
		
		// end condition: we are at the start position and the next neighbor is the same as the first one
		if ((contourX == loopX) && (contourY ==  loopY) && (nextNeighbor == contourFirstNeighbor)) {
			//then we are done
			done = YES;
		} else { // not at the start mark this pixel, if it is unmarked
			if (labels[(contourY * pixelsWide) + contourX] == 0) {
				labels[(contourY * pixelsWide) + contourX] = contourLabel;
				[[blobs objectAtIndex:contourLabel] addPixel:NSMakePoint(contourX, contourY) withValue:srcBytes[contourXYDataPosition]];		
			}
		}
	} while (!done);
	return YES;
}

-(BOOL)externalContour
{
	// start the contour, use neighbor 7 for external start neighbor
	// this is per the algo spec
	contourNeighborCheckIndex = 7;
	return [self contour];
}

-(BOOL)internalContour
{
	// start the contour, use neighbor 3 for internal start neighbor
	// this is per the algo spec
	contourNeighborCheckIndex = 3;
	return [self contour];
}

-(int)findNextNeighbor
{
	// finds the next edge, and marks the non-blob points as it goes
	// returns a number from 0 to 7 which is the neighbor from the startPosition that is the next edge
	// returns -1 if there are no valid blob pixel neighbors
	// this alters the instance variable contourNeighborCheckIndex to the direction of the next neighbor
	// it also returns it, although we could really just return any non -1 number
	
	// start the search at startNeighbor
	int startNeighbor = contourNeighborCheckIndex;
	do {
		if ([self validNeighborPixel]) {
			// it is! return the current neighbor
			return contourNeighborCheckIndex; // shunt out
		}
		// nope, mark it and increment the neighbor
		// this is a bit ugly
		labels[((contourY + yGrid[contourNeighborCheckIndex]) * pixelsWide) + (contourX + xGrid[contourNeighborCheckIndex])] = -1;
		// increment the neighborIndex around the clock
		contourNeighborCheckIndex ++;
		if (contourNeighborCheckIndex == 8) contourNeighborCheckIndex = 0;

	} while (contourNeighborCheckIndex != startNeighbor);

	// didnt find one, this is an isolated point
	return -1;
}

///////////////////////////
// BG image methods
///////////////////////////
-(NSImage*)bgImage
{
	return bgImage;
}

-(void)setBgImage:(NSImage*)anImage
{
	// sets the background image that gets subtracted from the foreground
	// i can use the first object in the reps because I know the cam is only adding a 
	// single rep. Altho this does work in the general case, usually
	NSBitmapImageRep * bitRep = [[anImage representations] objectAtIndex:0]; 
	
	// set up all the state vars here
	samplesPerPixel = [bitRep samplesPerPixel];
	bytesPerRow = [bitRep bytesPerRow];
	pixelsHigh = [bitRep pixelsHigh];
	pixelsWide = [bitRep pixelsWide];
	srcBytes = [bitRep bitmapData];
	maxDataPosition = pixelsHigh * bytesPerRow;
	
	// this should only need to be done once for any given image size	
	// but for now we do it every time we set the BG for simplicity sake
	[self setupNeighborGrid];
	
	[self setupStateArrays];
	// bitmapreps were never meant to be stored, so we will store the image instead
	[anImage retain];
	[bgImage release];
	bgImage = anImage;
}



- (void) dealloc
{
	free(labels);
	[blobs release];
	[super dealloc];
}


@end
